const tree = require('./binTree.js')

// 求二叉树的最大层数
function maxDepth(tree) {
    let max = 0
    // 二叉树的深度优先遍历，其实就是先序遍历
    const dfs = (root, level) => {
        // if (!n) return
        // console.log(n.val, level)
        // if (!n.left && !n.right) {
        //     max = Math.max(max, level)
        // }
        // dfs(n.left, level + 1)
        // dfs(n.right, level + 1)

        // 深度优先
        // 不使用递归的方法，记录每个节点的层级
        if (!root) return
        const stack = [[root, 1]]
        while (stack.length) {
            const [n, level] = stack.pop()
            // console.log(n.val)
            if (!n.left && !n.right) {
                max = Math.max(max, level)
            }
            if (n.right) {
                stack.push([n.right, level + 1])
            }
            if (n.left) {
                stack.push([n.left, level + 1])
            }
        }
    }

    dfs(tree, 1)
    return max
}

const res = maxDepth(tree)
console.log(res)